package com.cuz.array.binarysearch;

public class BinarySearch {

    /******
     * 0 1 2 3 4 5 6 7 8 9 10
     * l=-1 r=10
     * while(l+1!=r){
     *  m=Math.ceil(l+(h-l)/2);
     *  if(isBlue(m)){
     *  l=m
     *  }else{
     *      r=m
     *  }
     * }
     * return l or r
     *
     * 1.找到第一个大于 等于 5的数
     * B B B B B R R R R R  R
     * 0 1 2 3 4 5 6 7 8 9 10
     * 0到4 视为蓝色 5到 10 视为红色 isBlue==>>arr[m]<5 返回r
     *
     * 2.找到最后一个小于  5的数
     * B B B B B R R R R R  R
     * 0 1 2 3 4 5 6 7 8 9 10
     * 0到4 视为蓝色 5到 10 视为红色 isBlue==>>arr[m]<5 返回l
     *
     * 3.找到第一个大于  5的数
     * B B B B B B R R R R  R
     * 0 1 2 3 4 5 6 7 8 9 10
     * 0到5 视为蓝色 6到 10 视为红色 isBlue==>>arr[m]<=5 返回r
     *
     * 4.找到最后一个小于等于  5的数
     * B B B B B B R R R R  R
     * 0 1 2 3 4 5 6 7 8 9 10
     * 0到5 视为蓝色 6到 10 视为红色 isBlue==>>arr[m]<=5 返回l
     */

    public static int findFirstGreaterEqual(int[] ints, int target) {
        //target=4=> 1 2 3 3 || 4  5 6
        int l = -1;
        int r = ints.length;
        while (l + 1 != r) {
            int m = (int) (l + Math.ceil(r - l) / 2);
            if (ints[m] < target) {
                l = m;
            } else {
                r = m;
            }
        }
        return r < ints.length && ints[r] >= target ? r : -1;
    }

    public static int findLastLess(int[] ints, int target) {
        //target=4=> 1 2 3 3 || 4  5 6
        int l = -1;
        int r = ints.length;
        while (l + 1 != r) {
            int m = (int) (l + Math.ceil(r - l) / 2);
            if (ints[m] < target) {
                l = m;
            } else {
                r = m;
            }
        }
        return l >= 0 && ints[l] <= target ? l : -1;
    }

    public static int findLastGreater(int[] ints, int target) {
        //target=4=> 1 2 3 3  4 || 5 6
        int l = -1;
        int r = ints.length;
        while (l + 1 != r) {
            int m = (int) (l + Math.ceil(r - l) / 2);
            if (ints[m] <= target) {
                l = m;
            } else {
                r = m;
            }
        }
        return r < ints.length && ints[r] > target ? r : -1;
    }

    public static int findLastLessEqual(int[] ints, int target) {
        //target=4=> 1 2 3 3  4 || 5 6
        int l = -1;
        int r = ints.length;
        while (l + 1 != r) {
            int m = (int) (l + Math.ceil(r - l) / 2);
            if (ints[m] <= target) {
                l = m;
            } else {
                r = m;
            }
        }
        return l >= 0 && ints[l] <= target ? l : -1;
    }

    public static void main(String[] args) {
        int[] ints = {1, 2, 3, 4, 4, 4, 5, 5, 6};
        int firstGreaterEqual = findFirstGreaterEqual(ints, 7);
        int lastLessEqual = findLastLessEqual(ints, 7);
        int lastLess = findLastLess(ints, 7);
        int lastGreater = findLastGreater(ints, 7);
        printRes(ints,firstGreaterEqual);
        printRes(ints,lastLessEqual);
        printRes(ints,lastLess);
        printRes(ints,lastGreater);
    }

    static void printRes(int[] ints, int index) {
        if (index>=0&&index<ints.length){
            System.out.println(index+"===>"+ints[index]);
        }else {
            System.out.println(index+"===>"+"out of array");
        }
    }
}
